#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;
/**
 *442. 数组中重复的数据
中等
679
相关企业
给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]
示例 2：
输入：nums = [1,1,2]
输出：[1]
示例 3：
输入：nums = [1]
输出：[]
 * ***/
//原地哈希我似乎没有思路啊 ////我擦这个题不能这样写

// [4,3,2,7,8,2,3,1]
//  7 3 2 4 8 2 3 1
//  3 2 3 4 8 2 7 1
vector<int> findDuplicates(vector<int> &nums) {
    unordered_map<int, int> mp;

    vector<int> res;
    for (int i = 0; i < nums.size(); ++i) {
        if (mp.find(nums[i]) != mp.end()) {
            res.push_back(nums[i]);
        } else {
            ++mp[nums[i]];
        }

    }

    return res;
}

vector<int> findDuplicates1(vector<int> &nums) {

    //这个定理相对离谱吧 这种范围1-n的挖坑交换 总可以循环出去正常的都会归位
    int n = nums.size();

    for (int i = 0; i < n; ++i) {
        //这边应该是while 我他妈写成if了
        while (nums[i] != nums[nums[i] - 1]) {
            swap(nums[i], nums[i] - 1);
        }
    }

    vector<int> res;

    for (int i = 0; i < n; ++i) {

        if (nums[i] - 1 != i) {
            res.push_back(nums[i]);
        }


    }

    return res;
}